package com.modular.Shortest_path;

import java.util.*;

public class LC1514 {
    public static void main(String[] args) {

       // n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
        int n = 3;
        int [][]edges = new int[][]{{0,1},{1,2},{0,2}};
        double []succProb = new double[]{0.5,0.5,0.2};
        int start = 0;
        int end = 2;
        double v = new Solution15142().maxProbability1(n, edges, succProb, start, end);
        System.out.println(v);

    }
}

class Solution15142 {
    public double maxProbability1(int n, int[][] edges, double[] succProb, int start, int end) {
        //spfa方式 对bellman的改进
        //处理数据 https://leetcode-cn.com/problems/path-with-maximum-probability/solution/5211-gai-lu-zui-da-de-lu-jing-bellman-fordsuan-fa-/
        Map<Integer, Map<Integer, Double>> graph = new HashMap<>();
        int length = edges.length;
        for (int i = 0; i < length; i++) {
            int[] edge = edges[i];//获取当前边情况
            double point = succProb[i];
            Map<Integer, Double> a = graph.getOrDefault(edge[0], new HashMap<>());
            a.put(edge[1], point);
            graph.put(edge[0], a);

            Map<Integer, Double> b = graph.getOrDefault(edge[1], new HashMap<>());
            b.put(edge[0], point);
            graph.put(edge[1], b);
        }

        //double[] dist = new double[n];
        boolean[] visited = new boolean[n];
        //Arrays.fill(di, Integer.MIN_VALUE);
        //初始化为小顶堆，避免松弛
        Queue<Integer> q = new LinkedList<>();
      //  Queue<Integer> queue = new PriorityQueue<Integer>((a, b) -> (Double) (a[1] - b[1]));

        double [] f= new double[n];
        f[start] = 1.0;
        q.offer(start);
        visited[start] = true;
        while (!q.isEmpty()) {
            int tmp = q.poll();
            visited[tmp] = false;
            if (!graph.containsKey(tmp)) continue; //如果表中无直接继续
            Map<Integer, Double> t =  graph.get(tmp);
            for (int key : t.keySet()) {
                double val = t.get(key);
                if (f[key] < f[tmp] * val) {
                    f[key] = f[tmp] * val;
                    if (!visited[key]) {
                        q.offer(key);
                        visited[key] = true;
                    }
                }
            }
        }
        return f[end];

    }
    /*public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        double[] por = new double[n];
        por[start] = 1;
        while (true) {
            boolean flag = false;
            for (int i = 0; i < edges.length; i++) {
                if (por[edges[i][0]] * succProb[i] > por[edges[i][1]]) {
                    por[edges[i][1]] = por[edges[i][0]] * succProb[i];
                    flag = true;
                }
                if (por[edges[i][1]] * succProb[i] > por[edges[i][0]]) {
                    por[edges[i][0]] = por[edges[i][1]] * succProb[i];
                    flag = true;
                }
            }
            if (!flag) break;
        }
        return por[end];
    }*/
}




//地杰斯特拉堆优化
class Solution1514 {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        List<List<Pair>> graph = new ArrayList<List<Pair>>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<Pair>());
        }
        for (int i = 0; i < edges.length; i++) {
            int[] e = edges[i];
            //由于是无向图
            graph.get(e[0]).add(new Pair(succProb[i], e[1]));
            graph.get(e[1]).add(new Pair(succProb[i], e[0]));
        }

        PriorityQueue<Pair> que = new PriorityQueue<Pair>();
        //Queue<Pair> que = new LinkedList<>();
        double[] prob = new double[n];//存路径
        boolean []visit = new boolean[n];

        que.offer(new Pair(1, start));//到自己的路径长度初始化为1
        prob[start] = 1;
        while (!que.isEmpty()) {
            Pair pair = que.poll();//队头出队
            double pr = pair.probability;
            int node = pair.node;
            if(visit[node]) continue;
            visit[node] = true;
            for (Pair pairNext : graph.get(node)) {
                double prNext = pairNext.probability;
                int nodeNext = pairNext.node;
                if(prob[node]*prNext<prob[nodeNext]) continue;
                prob[nodeNext] = Math.max(prob[node]*prNext,prob[nodeNext]);
                que.offer(new Pair(prob[nodeNext], nodeNext));
            }
        }
        return prob[end];
    }
}
class Pair implements Comparable<Pair> {
    double probability;
    int node;

    public Pair(double probability, int node) {
        this.probability = probability;
        this.node = node;
    }

    public int compareTo(Pair pair2) {
        if (this.probability == pair2.probability) {
            return this.node - pair2.node;
        } else {
            return this.probability - pair2.probability > 0 ? -1 : 1;
        }
    }
}

//地杰斯特拉
class Solution15141 {
    class State {
        int node;
        double prob;

        public State(int node, double prob) {
            this.node = node;
            this.prob = prob;
        }
    }

    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        Map<Integer, Set<double[]>> map = new HashMap<>();

        for (int i = 0; i < edges.length; i++) {
            int a = edges[i][0], b = edges[i][1];
            if (!map.containsKey(a)) map.put(a, new HashSet<>());
            map.get(a).add(new double[] {b, succProb[i]});
            if (!map.containsKey(b)) map.put(b, new HashSet<>());
            map.get(b).add(new double[] {a, succProb[i]});
        }

        double[] probs = new double[n];
        Queue<State> queue = new LinkedList<>();
        queue.offer(new State(start, 1.0));

        while (!queue.isEmpty()) {
            State state = queue.poll();
            int curr = state.node;
            double prob = state.prob;

            Set<double[]> neighbours = map.getOrDefault(curr, new HashSet<>());
            for (double[] neighbour: neighbours) {
                if (probs[(int) neighbour[0]] >= prob * neighbour[1]) continue;

                queue.add(new State((int) neighbour[0], prob * neighbour[1]));
                probs[(int) neighbour[0]] = prob * neighbour[1];
            }
        }

        return probs[end];
    }


}


